The present invention relates to navigation systems and in particular to geographic data sets for use in navigation systems.
Computer-based navigation systems for use on land have become available in a variety of forms and provide for a variety of useful features. One exemplary type of navigation system uses (1) one or more detailed data sets that represent one or more geographic areas or regions, (2) a navigation application program, (3) appropriate computer hardware, such as a microprocessor, memory, and data storage, and, optionally, (4) a positioning system.
Referring to FIG. 1, there is a diagram illustrating a configuration of an exemplary navigation system 10. The navigation system 10 is a combination of hardware and software components which can be implemented in various different kinds of environments or on different platforms. For example, the navigation system 10 may be located in an automobile 12. In an exemplary embodiment, the navigation system 10 includes appropriate hardware 14 which may include a GPS system 16, an antenna 18, sensors 20 coupled to sense the vehicle speed and distance traveled, and a compass 22 to sense the vehicle direction. In addition, the navigation system includes an appropriate computer 24, including a CPU 26 and memory 28 as well as other appropriate hardware.
Included as part of the navigation system 10 is a drive 30 (or other suitable peripheral device) into which a data storage medium 32 can be installed. One or more geographic data sets 34 are stored on the storage medium 32. In one embodiment, the storage medium 32 is a CD-ROM disc. In another alternative embodiment, the storage medium 32 may be a PCMCIA card in which case the drive 30 would be substituted with a PCMCIA slot. Various other storage media may be used, including fixed or hard disks, DVD (digital video disks) or other currently available storage media, as well as storage media that may be developed in the future. The embodiments disclosed herein may be used in other types of navigation systems, as explained below.
The navigation system 10 also includes a user interface 40 coupled to the computer 24. The user interface 40 includes appropriate means for receiving instructions and input from an end-user as well as means for providing information back to the end-user. For example, the user interface 40 may include an input panel or keyboard into which an end-user may indicate a selection of a destination. The user interface 40 may also include a display or speakers (including speech synthesis hardware and software) by which the user can be informed of navigation information. For visual navigation information, the user interface 40 may provide features allowing the user to zoom a display in on or out of a particular geographic area to alternately display a larger geographic area or more detailed geographic information.
The positioning system may employ any of several well-known technologies to determine or approximate the end-user""s physical locations in a geographic region. For example, the positioning system may employ a GPS-type system (global positioning system), a dead reckoning-type system, or combinations of these, or other systems, all of which are well-known in the art.
All of the components described above may be conventional (or other than conventional) and the manufacture and use of these components are known to those of skill in the art.
The navigation system 10 includes another data storage device 36 (or ROM) which is used to store a navigation application program 38. (Alternatively, the application program 38 may be provided on the same storage device or medium 32 as the geographic data sets 34.) The navigation application program 38 is a software program that uses the geographic data set 34 and the positioning system (when employed). The navigation application program 38 may include separate applications (or subprograms). These subprograms provide various navigation features to the end-user of the navigation system 10. These features may include route calculation functions, maneuver generation functions, map display functions, vehicle positioning functions, destination resolution capabilities, and so on. The navigation features are provided to the end-user (e.g., the vehicle driver) by means of the user interface 40. The navigation application program 38 may be written in a suitable computer programming language such as C, although other programming languages are also suitable.
During a typical usage of the navigation system 10 of FIG. 1, the navigation application program 38 is loaded from the ROM 36 into the memory 28 associated with the processor 26. The computer 24 receives input from the user interface 40. The input may include a request for navigation information. The computer 24 receives information from the positioning system hardware 14. The information from the hardware 14 is used by the navigation application software 38 to determine the location, direction, speed, etc., of the vehicle 12. The navigation application program 38 may provide the end-user with a graphical display (e.g. a xe2x80x9cmapxe2x80x9d) of the end-user""s specific location in the geographic region. In addition, the navigation application program may provide the end-user with specific directions to locations in the geographic area from wherever the end-user is located.
To provide these various navigation application features, the navigation system 10 uses the geographic data 34 stored on the storage medium 32, optionally in conjunction with the output from the positioning system hardware 14. The geographic data 34 may be in the form of one or more computer-readable files or databases that enable the navigation application program 38 to provide the supported features. For example, to enable the calculation of a route between two locations in the geographic region, the geographic data 34 may include route calculation data that includes the positions of roads and intersections in the geographic region, information about one-way streets, turn restrictions, stop signs, stop lights, speed limits, and so on.
When performing a map display function with the navigation system, the sizes, shapes, and relative positions of geographic features in a portion of a geographic region are portrayed on the display of the user interface 40. These geographic features may include roads, intersections, and points-of-interest, as well as other features, such as lakes, railroad tracks, buildings, airports, stadiums, parks, mountain ranges, docks, ferries, tunnels, bridges, and so on. To provide this map display function, the geographic data set 34 may include cartographic data which allows the navigation application program 38 to display maps illustrating the size, shape, position, and character of these various geographic features on an attached display device. Zooming and panning of the displayed areas may also be supported.
Referring to FIG. 2, there is a diagram illustrating an exemplary configuration of a cartographic data set 34(carto) used for map display. The data set 34(carto) is part of the geographic data set 34 of FIG. 1 which may include other kinds of data sets used for route calculation, maneuver generation, and other navigation functions. In FIG. 2, the data set 34(carto) includes a (sub)set 42 of road segment data entities, e.g. seg(1), seg(2) . . . seg(n). Each road segment data entity represents a portion of a roadway in the geographic region. Associated with each road segment data entity record, seg( ), are data (such as nodes and attributes 46(1), 46(2) . . . 46(n)) that facilitate portraying the respective represented road portions on the computer display device. The road segment data entities, seg(1), seg(2) . . . seg(n), may be implemented using standard types of data structures used in database construction.
Referring to FIG. 3, there is a map diagram illustrating a portion of the geographic region represented by the geographic data set 34. This portion shows roadways of both straight, 52S1, 52S2, and other-than-straight (e.g. curved), 52C1, types. For purposes of storing the necessary information to display this portion of the geographic region, nodes are identified along the roadways. Nodes are identified where two roads intersect or where any of the attributes associated with a portion of the road change, such as when a road enters a school zone and the speed limit changes. In the data set 34, each of the road segment entity records is associated with the two nodes (and/or the geographical coordinates of the nodes) that correspond to the locations of the end points of the road portion represented by the road segment entity record, as illustrated at 46( ) in FIG. 2. Also associated with the road segment entity record in the cartographic data set 34(carto) is other information necessary to portray the road portion, as also illustrated at 46( ) in FIG. 2.
For straight road portions, e.g. 52S1, 52S2 in FIG. 3, portraying the shape of a road portion can be done by generating a straight line linking the end points (i.e., nodes) identified by the segment data entity record that represents the road portion. However, when the road portion is other-than-straight, it is required that the geographic database include additional information to display the shape of the road portion.
In the map of FIG. 3, there is shown the curved road portion 52C1 represented by seg(m) which has end points, represented by LN(m) and RN(m). FIG. 4 shows a diagram of a road segment data record, seg(m) in the data set 34(carto) used to represent the curved road portion 52C1 in FIG. 3. Associated with the road segment data entity seg(m) are node data 48 that include the latitude and longitude coordinate positions of the two end points, LN(m) and RN(m) of the represented road portion 52C1. In one known geographic database for a navigation system, curving geographic features are represented using shape points. FIG. 3 shows exemplary shape points SP(m)(1), SP(m)(2), SP(m)(3), and SP(m)(n) located along the portion of the road 52C1 represented by the data entity seg(m). Using this method, in addition to the node data, the geographic data set 34 also stores data corresponding to these shape points that fall along the curving geographic feature. In FIG. 4, the road segment data entity seg(m) is associated with shape points 50 (SP(m)(1), SP(m)(2) . . . SP(m)(n)) which store latitude and longitude coordinates for each of the shape points located along the curved road portion 52C1. These shape points are used for several purposes in the geographic database and by the navigation application that uses it. For example, shape points are used to approximate the curving shape of the represented portion of the road on the computer display. The curving geographic feature is reproduced on the display by drawing straight lines from shape point to shape point starting and ending with the end points. The number of shape points stored between a given set of end points depends on the shape of the curve and the accuracy or resolution desired in the reproduced display. Shape points are also used by the navigation application for vehicle positioning along curved road portions, where accuracy is important. (Although the terminology xe2x80x9cshape pointxe2x80x9d is used in this specification, it is understood that other terminology could be used to refer to a position or locus along a straight or curving geographic feature.)
The description provided above relates to the portrayal of other-than-straight portions of roadways. Similar considerations apply to the portrayal of other geographic features in the form of lines or polygons, such as ponds, railroad tracks, buildings, airports, stadiums, parks, mountain ranges, docks, ferries, tunnels, bridges, and so on. Shape points are selected along the lengths or boundaries of these kinds of geographic features, stored, and used to portray the feature on a computer display.
While using shape points to represent the shape of an other-than-straight geographic feature has the advantage that it is conceptually relatively simple to work with in database development, compilation, access and display software, it has several drawbacks. Storing these additional data for displaying other-than-straight geographic features increases the data storage requirements of the geographic data sets. Even with modest accuracy requirements, five to ten percent of each database may be dedicated to shape point data. Moreover, this percentage increases in direct proportion to any increase in accuracy requirements. Further, since shape information represents a much larger percentage of those geographic data subsets used for map display and to infer the vehicle""s position, the negative impact on RAM memory size requirements and database read time is proportionately even greater.
Accordingly, there is a need in navigation systems to provide a method of representing and storing geographic feature information in such a way as to minimize the storage requirements while providing a high level of accuracy in the representation of other-than-straight features. Further, it is desired that the increases in resolution and accuracy in a geographic data set do not negatively impact on RAM memory size or operating performance requirements of a navigation system.
Therefore, it is an objective to provide an improved method for representing and storing geographic feature information that provides for highly accurate representation of geographic features, minimal storage requirements and minimal impact on hardware configuration requirements.
To achieve the foregoing and other objectives and in accordance with the purposes of the present invention, there is provided a system and method for storing data to represent other-than-straight map features in a computer-readable geographic database for use in a navigation system. For geographic features that are other-than-straight, a curve generated by a computable function is fitted to an image of the other-than-straight map feature. The computable function may be a polynomial equation whose shape is defined by its coefficients. In one embodiment, the polynomial equation is a spline curve, and in particular a Bezier curve whose shape is defined by control points. The coefficients of the polynomial equation are associated with data representing the other-than-straight feature. In the case in which the polynomial equation is a Bezier curve, the control points for generating the Bezier curve are associated with the data representing the other-than-straight feature. These control points are stored in the geographic database and are used in displaying the other-than-straight geographic feature. Use of a computable function to generate other-than-straight geographic features and storing parameters to be used by the computable function has the potential for significantly reducing the storage requirements for representing other-than-straight features in a geographic database.
According to a further aspect, normalized control point pairs are stored in a data structure and an index reference into the data structure is associated with data used to represent the other-than-straight geographic feature, thereby resulting in further reduction in data storage requirements.